


/*-------------------------------------------------------------------------
 *
 * rangetypes_spgist.c
 *	  2D点映射范围的四叉树实现，用于SP-GiST。
 *
 * 四叉树是一种类似于二叉树的数据结构，但适应于
 * 2D数据。每个内节点的四叉树包含一个点（重心），
 * 将2D空间划分为4个象限。每个象限与一个
 * 子节点相关联。
 *
 * 范围映射到2D点，以便下界是一个维度，
 * 上界是另一个维度。按照惯例，我们将下界
 * 视为水平轴，上界视为垂直轴。
 *
 * 这种映射的一个特别之处在于对空范围的处理。
 * 空范围没有下界和上界，所以无法以
 * 直接的方式映射到2D空间。为了解决这个问题，
 * 根节点可以拥有一个第五个
 * 象限，专门用于空范围。此外，树中的
 * 内节点可以没有重心。它们仅包含两个子节点，
 * 一个用于空范围，另一个用于非空范围。
 * 这样的节点可以出现在根节点，也可以
 * 在根节点的第五个子节点下出现（在这种情况下
 * 它将仅包含空节点）。
 *
 * SP-GiST的picksplit函数使用沿两个轴的中位数作为重心。
 * 此实现仅使用范围元素数据类型的比较函数，
 * 因此适用于任何范围类型。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/utils/adt/rangetypes_spgist.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/spgist.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "utils/builtins.h"
#include "utils/datum.h"
#include "utils/rangetypes.h"

static int16 fc_getQuadrant(TypeCacheEntry *fc_typcache, const RangeType *fc_centroid,
						 const RangeType *fc_tst);
static int	fc_bound_cmp(const void *fc_a, const void *fc_b, void *fc_arg);

static int	fc_adjacent_inner_consistent(TypeCacheEntry *fc_typcache,
									  const RangeBound *fc_arg, const RangeBound *fc_centroid,
									  const RangeBound *fc_prev);
static int	fc_adjacent_cmp_bounds(TypeCacheEntry *fc_typcache, const RangeBound *fc_arg,
								const RangeBound *fc_centroid);

/*
 * SP-GiST 'config' 接口函数。
 */
Datum spg_range_quad_config(PG_FUNCTION_ARGS)
{
	/* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
	spgConfigOut *fc_cfg = (spgConfigOut *) PG_GETARG_POINTER(1);

	fc_cfg->prefixType = ANYRANGEOID;
	fc_cfg->labelType = VOIDOID;	/* 我们不需要节点标签 */
	fc_cfg->canReturnData = true;
	fc_cfg->longValuesOK = false;
	PG_RETURN_VOID();
}

/*----------
 * 确定 2D 映射范围相对于质心的象限。
 *
 * 象限编号如下：
 *
 *	 4	|  1
 *	----+----
 *	 3	|  2
 *
 * 其中范围的下界为水平轴，上界为垂直轴。
 *
 * 位于某一轴上的范围被视为位于在垂直轴上值更高的象限。也就是说，水平轴上的值被视为属于象限 1 或 4，垂直轴上的值被视为属于象限 1 或 2。与质心相等的范围被视为位于象限 1。
 *
 * 空范围被视为位于特殊象限 5。
 *----------
 */
static int16 fc_getQuadrant(TypeCacheEntry *fc_typcache, const RangeType *fc_centroid, const RangeType *fc_tst)
{
	RangeBound	fc_centroidLower,
				fc_centroidUpper;
	bool		fc_centroidEmpty;
	RangeBound	fc_lower,
				fc_upper;
	bool		fc_empty;

	range_deserialize(fc_typcache, fc_centroid, &fc_centroidLower, &fc_centroidUpper,
					  &fc_centroidEmpty);
	range_deserialize(fc_typcache, fc_tst, &fc_lower, &fc_upper, &fc_empty);

	if (fc_empty)
		return 5;

	if (range_cmp_bounds(fc_typcache, &fc_lower, &fc_centroidLower) >= 0)
	{
		if (range_cmp_bounds(fc_typcache, &fc_upper, &fc_centroidUpper) >= 0)
			return 1;
		else
			return 2;
	}
	else
	{
		if (range_cmp_bounds(fc_typcache, &fc_upper, &fc_centroidUpper) >= 0)
			return 4;
		else
			return 3;
	}
}

/*
 * 选择 SP-GiST 函数：选择添加新范围的路径。
 */
Datum spg_range_quad_choose(PG_FUNCTION_ARGS)
{
	spgChooseIn *fc_in = (spgChooseIn *) PG_GETARG_POINTER(0);
	spgChooseOut *fc_out = (spgChooseOut *) PG_GETARG_POINTER(1);
	RangeType  *fc_inRange = DatumGetRangeTypeP(fc_in->datum),
			   *fc_centroid;
	int16		fc_quadrant;
	TypeCacheEntry *fc_typcache;

	if (fc_in->allTheSame)
	{
		fc_out->resultType = spgMatchNode;
		/* 好的，它通过了 -> 让我们计算距离 */
		fc_out->result.matchNode.levelAdd = 0;
		fc_out->result.matchNode.restDatum = RangeTypePGetDatum(fc_inRange);
		PG_RETURN_VOID();
	}

	fc_typcache = range_get_typcache(fcinfo, RangeTypeGetOid(fc_inRange));

	/*
	 * 没有质心的节点仅根据范围是否为空来划分范围。
	 * 所有空范围转到子节点 0，所有非空范围转到节点 1。
	 */
	if (!fc_in->hasPrefix)
	{
		fc_out->resultType = spgMatchNode;
		if (RangeIsEmpty(fc_inRange))
			fc_out->result.matchNode.nodeN = 0;
		else
			fc_out->result.matchNode.nodeN = 1;
		fc_out->result.matchNode.levelAdd = 1;
		fc_out->result.matchNode.restDatum = RangeTypePGetDatum(fc_inRange);
		PG_RETURN_VOID();
	}

	fc_centroid = DatumGetRangeTypeP(fc_in->prefixDatum);
	fc_quadrant = fc_getQuadrant(fc_typcache, fc_centroid, fc_inRange);

	Assert(fc_quadrant <= fc_in->nNodes);

	/* 选择与象限编号匹配的节点 */
	fc_out->resultType = spgMatchNode;
	fc_out->result.matchNode.nodeN = fc_quadrant - 1;
	fc_out->result.matchNode.levelAdd = 1;
	fc_out->result.matchNode.restDatum = RangeTypePGetDatum(fc_inRange);

	PG_RETURN_VOID();
}

/*
 * 用于排序的边界比较。
 */
static int fc_bound_cmp(const void *fc_a, const void *fc_b, void *fc_arg)
{
	RangeBound *fc_ba = (RangeBound *) fc_a;
	RangeBound *fc_bb = (RangeBound *) fc_b;
	TypeCacheEntry *fc_typcache = (TypeCacheEntry *) fc_arg;

	return range_cmp_bounds(fc_typcache, fc_ba, fc_bb);
}

/*
 * Picksplit SP-GiST 函数：将范围拆分成节点。选择 "质心"
 * 范围并根据象限分配范围。
 */
Datum spg_range_quad_picksplit(PG_FUNCTION_ARGS)
{
	spgPickSplitIn *fc_in = (spgPickSplitIn *) PG_GETARG_POINTER(0);
	spgPickSplitOut *fc_out = (spgPickSplitOut *) PG_GETARG_POINTER(1);
	int			fc_i;
	int			fc_j;
	int			fc_nonEmptyCount;
	RangeType  *fc_centroid;
	bool		fc_empty;
	TypeCacheEntry *fc_typcache;

	/* 使用下界和上界的中位数作为质心范围 */
	RangeBound *fc_lowerBounds,
			   *fc_upperBounds;

	fc_typcache = range_get_typcache(fcinfo,
								  RangeTypeGetOid(DatumGetRangeTypeP(fc_in->datums[0])));

	/* 为范围分配内存 */
	fc_lowerBounds = palloc(sizeof(RangeBound) * fc_in->nTuples);
	fc_upperBounds = palloc(sizeof(RangeBound) * fc_in->nTuples);
	fc_j = 0;

	/* 反序列化范围的边界，计算非空范围 */
	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
	{
		range_deserialize(fc_typcache, DatumGetRangeTypeP(fc_in->datums[fc_i]),
						  &fc_lowerBounds[fc_j], &fc_upperBounds[fc_j], &fc_empty);
		if (!fc_empty)
			fc_j++;
	}
	fc_nonEmptyCount = fc_j;

	/*
	 * 所有范围都是空的。我们能做的最好的事情是构建一个没有
	 * 质心的内部节点，并将所有范围放入节点 0。如果后续添加
	 * 非空范围，它们将被路由到节点 1。
	 */
	if (fc_nonEmptyCount == 0)
	{
		fc_out->nNodes = 2;
		fc_out->hasPrefix = false;
		/* 前缀为空 */
		fc_out->prefixDatum = PointerGetDatum(NULL);
		fc_out->nodeLabels = NULL;

		fc_out->mapTuplesToNodes = palloc(sizeof(int) * fc_in->nTuples);
		fc_out->leafTupleDatums = palloc(sizeof(Datum) * fc_in->nTuples);

		/* 将所有范围放入节点 0 */
		for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
		{
			RangeType  *fc_range = DatumGetRangeTypeP(fc_in->datums[fc_i]);

			fc_out->leafTupleDatums[fc_i] = RangeTypePGetDatum(fc_range);
			fc_out->mapTuplesToNodes[fc_i] = 0;
		}
		PG_RETURN_VOID();
	}

	/* 按顺序排序范围边界以找到中位数 */
	qsort_arg(fc_lowerBounds, fc_nonEmptyCount, sizeof(RangeBound),
			  fc_bound_cmp, fc_typcache);
	qsort_arg(fc_upperBounds, fc_nonEmptyCount, sizeof(RangeBound),
			  fc_bound_cmp, fc_typcache);

	/* 从下界和上界的中位数构造 "质心" 范围 */
	fc_centroid = range_serialize(fc_typcache, &fc_lowerBounds[fc_nonEmptyCount / 2],
							   &fc_upperBounds[fc_nonEmptyCount / 2], false);
	fc_out->hasPrefix = true;
	fc_out->prefixDatum = RangeTypePGetDatum(fc_centroid);

	/* 仅当它是根节点时创建空范围的节点 */
	fc_out->nNodes = (fc_in->level == 0) ? 5 : 4;
	fc_out->nodeLabels = NULL;		/* 我们不需要节点标签 */

	fc_out->mapTuplesToNodes = palloc(sizeof(int) * fc_in->nTuples);
	fc_out->leafTupleDatums = palloc(sizeof(Datum) * fc_in->nTuples);

	/*
	 * 根据相对于 "质心" 范围的象限将范围分配给相应的节点。
	 */
	for (fc_i = 0; fc_i < fc_in->nTuples; fc_i++)
	{
		RangeType  *fc_range = DatumGetRangeTypeP(fc_in->datums[fc_i]);
		int16		fc_quadrant = fc_getQuadrant(fc_typcache, fc_centroid, fc_range);

		fc_out->leafTupleDatums[fc_i] = RangeTypePGetDatum(fc_range);
		fc_out->mapTuplesToNodes[fc_i] = fc_quadrant - 1;
	}

	PG_RETURN_VOID();
}

/*
 * SP-GiST 一致性函数用于内部节点：检查哪些节点与给定查询集一致。
 */
Datum spg_range_quad_inner_consistent(PG_FUNCTION_ARGS)
{
	spgInnerConsistentIn *fc_in = (spgInnerConsistentIn *) PG_GETARG_POINTER(0);
	spgInnerConsistentOut *fc_out = (spgInnerConsistentOut *) PG_GETARG_POINTER(1);
	int			fc_which;
	int			fc_i;
	MemoryContext fc_oldCtx;

	/*
	 * 对于相邻搜索，我们还需要先前的质心（如果有），以提高
	 * 一致性检查的准确性。在这种情况下，needPrevious 标志
	 * 被设置并且质心被传递到 traversalValue 中。
	 */
	bool		fc_needPrevious = false;

	if (fc_in->allTheSame)
	{
		/* 报告所有节点都应该被访问 */
		fc_out->nNodes = fc_in->nNodes;
		fc_out->nodeNumbers = (int *) palloc(sizeof(int) * fc_in->nNodes);
		for (fc_i = 0; fc_i < fc_in->nNodes; fc_i++)
			fc_out->nodeNumbers[fc_i] = fc_i;
		PG_RETURN_VOID();
	}

	if (!fc_in->hasPrefix)
	{
		/*
		 * 这个内部节点没有质心。这样的节点有两个子节点，
		 * 第一个用于空范围，第二个用于非空范围。
		 */
		Assert(fc_in->nNodes == 2);

		/*
		 * 哪个变量的第 N 位意味着 (N - 1) 节点应该被访问。
		 * 最初，所有位都被设置。应该被跳过的节点的位将被取消设置。
		 */
		fc_which = (1 << 1) | (1 << 2);
		for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
		{
			StrategyNumber fc_strategy = fc_in->scankeys[fc_i].sk_strategy;
			bool		fc_empty;

			/*
			 * 当操作符的第二个参数不是范围时，唯一的策略是
			 * RANGESTRAT_CONTAINS_ELEM。
			 */
			if (fc_strategy != RANGESTRAT_CONTAINS_ELEM)
				fc_empty = RangeIsEmpty(DatumGetRangeTypeP(fc_in->scankeys[fc_i].sk_argument));
			else
				fc_empty = false;

			switch (fc_strategy)
			{
				case RANGESTRAT_BEFORE:
				case RANGESTRAT_OVERLEFT:
				case RANGESTRAT_OVERLAPS:
				case RANGESTRAT_OVERRIGHT:
				case RANGESTRAT_AFTER:
				case RANGESTRAT_ADJACENT:
					/* 如果任何参数为空，这些策略将返回 false */
					if (fc_empty)
						fc_which = 0;
					else
						fc_which &= (1 << 2);
					break;

				case RANGESTRAT_CONTAINS:

					/*
					 * 所有范围都包含一个空范围。只有非空
					 * 范围可以包含一个非空范围。
					 */
					if (!fc_empty)
						fc_which &= (1 << 2);
					break;

				case RANGESTRAT_CONTAINED_BY:

					/*
					 * 只有空范围被空范围包含。
					 * 空范围和非空范围都可以被一个
					 * 非空范围包含。
					 */
					if (fc_empty)
						fc_which &= (1 << 1);
					break;

				case RANGESTRAT_CONTAINS_ELEM:
					fc_which &= (1 << 2);
					break;

				case RANGESTRAT_EQ:
					if (fc_empty)
						fc_which &= (1 << 1);
					else
						fc_which &= (1 << 2);
					break;

				default:
					elog(ERROR, "unrecognized range strategy: %d", fc_strategy);
					break;
			}
			if (fc_which == 0)
				break;			/* 不需要考虑其余条件 */
		}
	}
	else
	{
		RangeBound	fc_centroidLower,
					fc_centroidUpper;
		bool		fc_centroidEmpty;
		TypeCacheEntry *fc_typcache;
		RangeType  *fc_centroid;

		/* 这个节点有一个质心。获取它。 */
		fc_centroid = DatumGetRangeTypeP(fc_in->prefixDatum);
		fc_typcache = range_get_typcache(fcinfo,
									  RangeTypeGetOid(DatumGetRangeTypeP(fc_centroid)));
		range_deserialize(fc_typcache, fc_centroid, &fc_centroidLower, &fc_centroidUpper,
						  &fc_centroidEmpty);

		Assert(fc_in->nNodes == 4 || fc_in->nNodes == 5);

		/*
		 * 哪个变量的第 N 位意味着 (N - 1) 节点 (第 N 象限)
		 * 应该被访问。最初，所有位都被设置。可以
		 * 跳过的节点的位将被取消设置。
		 */
		fc_which = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5);

		for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
		{
			StrategyNumber fc_strategy;
			RangeBound	fc_lower,
						fc_upper;
			bool		fc_empty;
			RangeType  *fc_range = NULL;

			RangeType  *fc_prevCentroid = NULL;
			RangeBound	fc_prevLower,
						fc_prevUpper;
			bool		fc_prevEmpty;

			/* 根据扫描策略对范围边界的限制 */
			RangeBound *fc_minLower = NULL,
					   *fc_maxLower = NULL,
					   *fc_minUpper = NULL,
					   *fc_maxUpper = NULL;

			/* 对范围边界的限制是否是包括的？ */
			bool		fc_inclusive = true;
			bool		fc_strictEmpty = true;
			int			fc_cmp,
						fc_which1,
						fc_which2;

			fc_strategy = fc_in->scankeys[fc_i].sk_strategy;

			/*
			 * RANGESTRAT_CONTAINS_ELEM 就像 RANGESTRAT_CONTAINS，
			 * 但参数是单个元素。将单个元素扩展为
			 * 包含该元素的范围，并将其视为
			 * RANGESTRAT_CONTAINS。
			 */
			if (fc_strategy == RANGESTRAT_CONTAINS_ELEM)
			{
				fc_lower.inclusive = true;
				fc_lower.infinite = false;
				fc_lower.lower = true;
				fc_lower.val = fc_in->scankeys[fc_i].sk_argument;

				fc_upper.inclusive = true;
				fc_upper.infinite = false;
				fc_upper.lower = false;
				fc_upper.val = fc_in->scankeys[fc_i].sk_argument;

				fc_empty = false;

				fc_strategy = RANGESTRAT_CONTAINS;
			}
			else
			{
				fc_range = DatumGetRangeTypeP(fc_in->scankeys[fc_i].sk_argument);
				range_deserialize(fc_typcache, fc_range, &fc_lower, &fc_upper, &fc_empty);
			}

			/*
			 * 大多数策略通过从搜索键形成一个边界框来处理，
			 * 由 minLower、maxLower、minUpper、maxUpper 定义。
			 * 有些直接修改 'which'，以准确地指定
			 * 需要访问的象限。
			 *
			 * 对于大多数策略，没有什么与空搜索键匹配，
			 * 并且空范围从不与非空键匹配。如果一个策略
			 * 在有关空范围时不这样表现，请将 strictEmpty 设置为
			 * false。
			 */
			switch (fc_strategy)
			{
				case RANGESTRAT_BEFORE:

					/*
					 * 如果范围 A 的上限低于范围 B 的下限，
					 * 则范围 A 在范围 B 之前。
					 */
					fc_maxUpper = &fc_lower;
					fc_inclusive = false;
					break;

				case RANGESTRAT_OVERLEFT:

					/*
					 * 如果范围 A 的上限小于或等于范围 B 的上限，
					 * 则范围 A 在范围 B 的左侧。
					 */
					fc_maxUpper = &fc_upper;
					break;

				case RANGESTRAT_OVERLAPS:

					/*
					 * 如果每个范围的下限低于或等于另一个
					 * 范围的上限，则非空范围重叠。
					 */
					fc_maxLower = &fc_upper;
					fc_minUpper = &fc_lower;
					break;

				case RANGESTRAT_OVERRIGHT:

					/*
					 * 如果范围 A 的下限大于或等于范围 B 的下限，
					 * 则范围 A 在范围 B 的右侧。
					 */
					fc_minLower = &fc_lower;
					break;

				case RANGESTRAT_AFTER:

					/*
					 * 如果范围 A 的下限大于范围 B 的上限，
					 * 则范围 A 在范围 B 之后。
					 */
					fc_minLower = &fc_upper;
					fc_inclusive = false;
					break;

				case RANGESTRAT_ADJACENT:
					if (fc_empty)
						break;	/* 跳到 strictEmpty 检查。 */

					/*
					 * 先前选择的象限可能排除下限或上限
					 * 相邻的可能性。如果存在以检查此
					 * 项，将反序列化先前的质心范围。
					 */
					if (fc_in->traversalValue)
					{
						fc_prevCentroid = DatumGetRangeTypeP(fc_in->traversalValue);
						range_deserialize(fc_typcache, fc_prevCentroid,
										  &fc_prevLower, &fc_prevUpper, &fc_prevEmpty);
					}

					/*
					 * 对于范围的上限与参数的下限相邻，
					 * 它将在 Y=lower 的相邻线（并且在其下方）上找到。
					 * 因此，如果参数的下限小于质心的
					 * 上限，则线落在第 2 和第 3 象限；如果
					 * 大于，则线落在第 1 和第 4 象限。（请参见
					 * adjacent_cmp_bounds 以获取边缘情况的描述）。
					 */
					fc_cmp = fc_adjacent_inner_consistent(fc_typcache, &fc_lower,
													&fc_centroidUpper,
													fc_prevCentroid ? &fc_prevUpper : NULL);
					if (fc_cmp > 0)
						fc_which1 = (1 << 1) | (1 << 4);
					else if (fc_cmp < 0)
						fc_which1 = (1 << 2) | (1 << 3);
					else
						fc_which1 = 0;

					/*
					 * 还要搜索与参数的上限相邻的范围。
					 * 它们将在 X=upper 的相邻线（并且在其右侧）上找到，
					 * 这落在第 3 和第 4，或第 1 和第 2 象限。
					 */
					fc_cmp = fc_adjacent_inner_consistent(fc_typcache, &fc_upper,
													&fc_centroidLower,
													fc_prevCentroid ? &fc_prevLower : NULL);
					if (fc_cmp > 0)
						fc_which2 = (1 << 1) | (1 << 2);
					else if (fc_cmp < 0)
						fc_which2 = (1 << 3) | (1 << 4);
					else
						fc_which2 = 0;

					/* 我们必须追踪与任一边界相邻的范围。 */
					fc_which &= fc_which1 | fc_which2;

					fc_needPrevious = true;
					break;

				case RANGESTRAT_CONTAINS:

					/*
					 * 非空范围 A 包含非空范围 B 当且仅当 A 的下限
					 * 小于或等于范围 B 的下限，并且范围 A 的上限
					 * 大于或等于范围 A 的上限。
					 *
					 * 所有非空范围都包含一个空范围。
					 */
					fc_strictEmpty = false;
					if (!fc_empty)
					{
						fc_which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
						fc_maxLower = &fc_lower;
						fc_minUpper = &fc_upper;
					}
					break;

				case RANGESTRAT_CONTAINED_BY:
					/* 包含的反义词。 */
					fc_strictEmpty = false;
					if (fc_empty)
					{
						/* 只有空范围被空范围包含 */
						fc_which &= (1 << 5);
					}
					else
					{
						fc_minLower = &fc_lower;
						fc_maxUpper = &fc_upper;
					}
					break;

				case RANGESTRAT_EQ:

					/*
					 * 相等的范围只能在与
					 * 参数所处相同的象限中。
					 */
					fc_strictEmpty = false;
					fc_which &= (1 << fc_getQuadrant(fc_typcache, fc_centroid, fc_range));
					break;

				default:
					elog(ERROR, "unrecognized range strategy: %d", fc_strategy);
					break;
			}

			if (fc_strictEmpty)
			{
				if (fc_empty)
				{
					/* 扫描键为空，没有分支满足条件 */
					fc_which = 0;
					break;
				}
				else
				{
					/* 不应访问含有空范围的树分支 */
					fc_which &= (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4);
				}
			}

			/*
			 * 使用边界框，查看我们必须深入到哪些象限。
			 */
			if (fc_minLower)
			{
				/*
				 * 如果质心的下限小于或等于
				 * 最小下限，则第 3 和第 4 象限中的任何内容
				 * 都将具有更小的下限，因此无法
				 * 匹配。
				 */
				if (range_cmp_bounds(fc_typcache, &fc_centroidLower, fc_minLower) <= 0)
					fc_which &= (1 << 1) | (1 << 2) | (1 << 5);
			}
			if (fc_maxLower)
			{
				/*
				 * 如果重心的下限大于最大下限，则第一和第二象限中的任何值也将具有大于或等于的下限，因此无法匹配。如果重心的下限等于最大下限，如果我们寻找的值严格大于最大值，我们仍然可以排除第一和第二象限。
				 */
				int			fc_cmp;

				fc_cmp = range_cmp_bounds(fc_typcache, &fc_centroidLower, fc_maxLower);
				if (fc_cmp > 0 || (!fc_inclusive && fc_cmp == 0))
					fc_which &= (1 << 3) | (1 << 4) | (1 << 5);
			}
			if (fc_minUpper)
			{
				/*
				 * 如果重心的上限小于或等于最小上限，则第二和第三象限中的任何值将具有更小的上限，因此无法匹配。
				 */
				if (range_cmp_bounds(fc_typcache, &fc_centroidUpper, fc_minUpper) <= 0)
					fc_which &= (1 << 1) | (1 << 4) | (1 << 5);
			}
			if (fc_maxUpper)
			{
				/*
				 * 如果重心的上限大于最大上限，则第一和第四象限中的任何值也将具有大于或等于的上限，因此无法匹配。如果重心的上限等于最大上限，如果我们寻找的值严格大于最大值，我们仍然可以排除第一和第四象限。
				 */
				int			fc_cmp;

				fc_cmp = range_cmp_bounds(fc_typcache, &fc_centroidUpper, fc_maxUpper);
				if (fc_cmp > 0 || (!fc_inclusive && fc_cmp == 0))
					fc_which &= (1 << 2) | (1 << 3) | (1 << 5);
			}

			if (fc_which == 0)
				break;			/* 不需要考虑其余条件 */
		}
	}

	/* 我们必须深入到由'wish'标识的象限中 */
	fc_out->nodeNumbers = (int *) palloc(sizeof(int) * fc_in->nNodes);
	if (fc_needPrevious)
		fc_out->traversalValues = (void **) palloc(sizeof(void *) * fc_in->nNodes);
	fc_out->nNodes = 0;

	/*
	 * traversalValues 的元素应分配在
	 * traversalMemoryContext 中
	 */
	fc_oldCtx = MemoryContextSwitchTo(fc_in->traversalMemoryContext);

	for (fc_i = 1; fc_i <= fc_in->nNodes; fc_i++)
	{
		if (fc_which & (1 << fc_i))
		{
			/* 如有需要，保存之前的前缀 */
			if (fc_needPrevious)
			{
				Datum		fc_previousCentroid;

				/*
				 * 我们知道，在此处 in->prefixDatum 是 varlena，
				 * 因为它是一个范围
				 */
				fc_previousCentroid = datumCopy(fc_in->prefixDatum, false, -1);
				fc_out->traversalValues[fc_out->nNodes] = (void *) fc_previousCentroid;
			}
			fc_out->nodeNumbers[fc_out->nNodes] = fc_i - 1;
			fc_out->nNodes++;
		}
	}

	MemoryContextSwitchTo(fc_oldCtx);

	PG_RETURN_VOID();
}

/*
 * adjacent_cmp_bounds
 *
 * 给定参数和重心边界，此函数确定与参数相邻的任何边界是否小于、或大于或等于重心。为简洁起见，我们将 arg < centroid 称为“左侧”，将 arg >= centroid 的情况称为“右侧”。这与象限的排列方式相对应，如果想象“左”相当于“下”，“右”相当于“上”。
 *
 * 对于“左”情况，返回 -1，对于“右”情况，返回 1。
 */
static int fc_adjacent_cmp_bounds(TypeCacheEntry *fc_typcache, const RangeBound *fc_arg,
					const RangeBound *fc_centroid)
{
	int			fc_cmp;

	Assert(fc_arg->lower != fc_centroid->lower);

	fc_cmp = range_cmp_bounds(fc_typcache, fc_arg, fc_centroid);

	if (fc_centroid->lower)
	{
		/*------
		 * 参数是上限，我们在寻找相邻的下限。匹配的相邻下限必须*大于*参数，但仅仅大于。
		 *
		 * 以下表格展示了固定参数边界和不同重心的期望结果。CMP 列显示 'cmp' 变量的值，ADJ 显示参数和重心是否相邻，依据 bounds_adjacent()。 (N) 意味着我们不需要检查该情况，因为它由 CMP 暗示。对于参数范围 [..., 500)，我们正在寻找的相邻范围是 [500, ...):
		 *
		 *	参数    重心			CMP   ADJ
		 *	[..., 500) [498, ...)	 >	  (N)	[500, ...) 在右侧
		 *	[..., 500) [499, ...)	 =	  (N)	[500, ...) 在右侧
		 *	[..., 500) [500, ...)	 <	   Y	[500, ...) 在右侧
		 *	[..., 500) [501, ...)	 <	   N	[500, ...) 在左侧
		 *
		 * 因此，当参数小于且不相邻于重心时，我们必须向左搜索。否则搜索右侧。
		 *------
		 */
		if (fc_cmp < 0 && !bounds_adjacent(fc_typcache, *fc_arg, *fc_centroid))
			return -1;
		else
			return 1;
	}
	else
	{
		/*------
		 * 该参数是下限，我们正在寻找相邻的上限。
		 * 匹配的相邻上限必须比该
		 * 参数 *小*，但仅仅小一点。
		 *
		 *	参数    质心		CMP   相邻
		 *	[500, ...) [..., 499)	 >	  (N)	[..., 500) 在右边
		 *	[500, ...) [..., 500)	 >	  (Y)	[..., 500) 在右边
		 *	[500, ...) [..., 501)	 =	  (N)	[..., 500) 在左边
		 *	[500, ...) [..., 502)	 <	  (N)	[..., 500) 在左边
		 *
		 * 当参数小于或等于
		 * 质心时，我们必须向左搜索。
		 * 否则向右搜索。我们不需要检查
		 * 参数是否与质心相邻，因为这
		 * 无关紧要。
		 *------
		 */
		if (fc_cmp <= 0)
			return -1;
		else
			return 1;
	}
}

/*----------
 * adjacent_inner_consistent
 *
 * 类似于 adjacent_cmp_bounds，但也考虑前一
 * 级的质心。我们可能在前一个
 * 节点中向左（或右）遍历，寻找与
 * 另一个边界相邻的范围，即使我们已经排除了
 * 在该方向上与该边界匹配的可能性。通过将
 * 参数与上一个质心进行比较，并将
 * 上一个质心与当前质心进行比较，我们可以确定
 * 我们在前一层应该向哪个方向移动，以及
 * 我们实际上移动了哪个方向。
 *
 * 如果左侧可以有任何匹配，返回 -1。如果右侧，
 * 返回 1。如果在这个质心下没有匹配，
 * 因为我们已经在前一层排除了它们，返回 0。
 *
 * XXX：仅比较前一个和当前级别并不是万无一失的；
 * 我们可能仍然会不必要地搜索某些分支。例如，假设
 * 我们在搜索值 15，并且我们遍历以下质心
 * （暂时仅考虑一个边界）：
 *
 * 第 1 层：20
 * 第 2 层：50
 * 第 3 层：25
 *
 * 此时，前一个质心是 50，当前质心是 25，
 * 目标值在左侧。但因为我们已经在第一层
 * 从质心 20 移动到 50，所以当前分支中不能
 * 有任何值 < 20。但仅通过查看前一个
 * 和当前质心，我们并不知道这一点，因此我们
 * 不必要地向左遍历。我们沿着这条分支的原因
 * 是我们在寻找与 *另一个*
 * 边界的匹配。如果我们明确跟踪我们正在寻找哪个边界，
 * 而不是从前一个和当前质心推断出来，我们可以
 * 避免一些不必要的工作。
 *----------
 */
static int fc_adjacent_inner_consistent(TypeCacheEntry *fc_typcache, const RangeBound *fc_arg,
						  const RangeBound *fc_centroid, const RangeBound *fc_prev)
{
	if (fc_prev)
	{
		int			fc_prevcmp;
		int			fc_cmp;

		/*
		 * 在前一层我们应该向哪个方向遍历，
		 * 左侧还是右侧？
		 */
		fc_prevcmp = fc_adjacent_cmp_bounds(fc_typcache, fc_arg, fc_prev);

		/* 我们实际上走了哪个方向？ */
		fc_cmp = range_cmp_bounds(fc_typcache, fc_centroid, fc_prev);

		/* 如果两者不一致，这里没什么好看的 */
		if ((fc_prevcmp < 0 && fc_cmp >= 0) || (fc_prevcmp > 0 && fc_cmp < 0))
			return 0;
	}

	return fc_adjacent_cmp_bounds(fc_typcache, fc_arg, fc_centroid);
}

/*
 * SP-GiST 对于叶节点的一致性函数：检查叶值是否与查询
 * 使用相应的函数。
 */
Datum spg_range_quad_leaf_consistent(PG_FUNCTION_ARGS)
{
	spgLeafConsistentIn *fc_in = (spgLeafConsistentIn *) PG_GETARG_POINTER(0);
	spgLeafConsistentOut *fc_out = (spgLeafConsistentOut *) PG_GETARG_POINTER(1);
	RangeType  *fc_leafRange = DatumGetRangeTypeP(fc_in->leafDatum);
	TypeCacheEntry *fc_typcache;
	bool		fc_res;
	int			fc_i;

	/* 所有测试都是精确的 */
	fc_out->recheck = false;

	/* leafDatum 就是它本身... */
	fc_out->leafValue = fc_in->leafDatum;

	fc_typcache = range_get_typcache(fcinfo, RangeTypeGetOid(fc_leafRange));

	/* 执行所需的比较 */
	fc_res = true;
	for (fc_i = 0; fc_i < fc_in->nkeys; fc_i++)
	{
		Datum		fc_keyDatum = fc_in->scankeys[fc_i].sk_argument;

		/* 调用与扫描策略相对应的函数 */
		switch (fc_in->scankeys[fc_i].sk_strategy)
		{
			case RANGESTRAT_BEFORE:
				fc_res = range_before_internal(fc_typcache, fc_leafRange,
											DatumGetRangeTypeP(fc_keyDatum));
				break;
			case RANGESTRAT_OVERLEFT:
				fc_res = range_overleft_internal(fc_typcache, fc_leafRange,
											  DatumGetRangeTypeP(fc_keyDatum));
				break;
			case RANGESTRAT_OVERLAPS:
				fc_res = range_overlaps_internal(fc_typcache, fc_leafRange,
											  DatumGetRangeTypeP(fc_keyDatum));
				break;
			case RANGESTRAT_OVERRIGHT:
				fc_res = range_overright_internal(fc_typcache, fc_leafRange,
											   DatumGetRangeTypeP(fc_keyDatum));
				break;
			case RANGESTRAT_AFTER:
				fc_res = range_after_internal(fc_typcache, fc_leafRange,
										   DatumGetRangeTypeP(fc_keyDatum));
				break;
			case RANGESTRAT_ADJACENT:
				fc_res = range_adjacent_internal(fc_typcache, fc_leafRange,
											  DatumGetRangeTypeP(fc_keyDatum));
				break;
			case RANGESTRAT_CONTAINS:
				fc_res = range_contains_internal(fc_typcache, fc_leafRange,
											  DatumGetRangeTypeP(fc_keyDatum));
				break;
			case RANGESTRAT_CONTAINED_BY:
				fc_res = range_contained_by_internal(fc_typcache, fc_leafRange,
												  DatumGetRangeTypeP(fc_keyDatum));
				break;
			case RANGESTRAT_CONTAINS_ELEM:
				fc_res = range_contains_elem_internal(fc_typcache, fc_leafRange,
												   fc_keyDatum);
				break;
			case RANGESTRAT_EQ:
				fc_res = range_eq_internal(fc_typcache, fc_leafRange,
										DatumGetRangeTypeP(fc_keyDatum));
				break;
			default:
				elog(ERROR, "unrecognized range strategy: %d",
					 fc_in->scankeys[fc_i].sk_strategy);
				break;
		}

		/*
		 * 如果叶数据与查询键不匹配，则无需检查
		 * 后续键。
		 */
		if (!fc_res)
			break;
	}

	PG_RETURN_BOOL(fc_res);
}
